package com.qjc.demo.algorithm;

/**
 * @ClassName: SqrtX
 * @Description: 在不使用sqrt(x)函数的情况下，得到x的平方根的整数部分（x是正整数）。
 * 重点考察：二分法、牛顿迭代
 * @Author: qjc
 * @Date: 2022/5/5 4:53 PM
 */
public class SqrtX {

    // 通过二分查找计算，时间复杂度O(log n)
    public static int binarySearch(int x) {
        // l代表左指针，r代表右指针
        int index = -1, l = 0, r = x;
        while (l <= r) {
            int mid = l + (r - l) / 2;  // 计算l到r的中间值，就是l加上(r-l)的一半
            if (mid * mid <= x) {
                // 表示满足条件，但不一定是最接近的，所以需要移动指针
                index = mid;
                // 左指针右移
                l = mid + 1;
            } else {
                // 右指针左移
                r = mid - 1;
            }
        }
        return index;
    }

    // 牛顿迭代算法
    public static int newton(int x) {
        if (x == 0) return 0;
        return (int) sqrt(x, x);
    }

    private static double sqrt(double i, int x) {
        double rex = (i + x / i) / 2;
        if (rex == i) {
            return i;
        } else {
            return sqrt(rex, x);
        }
    }


    public static void main(String[] args) {
        System.out.println(binarySearch(24));
        System.out.println(newton(24));
    }

}
